Houzz front end interview prep

I. Ways to improve website performance

Minimize HTTP Requests

Too many external files in <head> will cause slow loading, we can
- combine all *.js to a file, *.css to a file
- use css spirit
CDN, putting static files over the world
Reduce image size
1. change resolution
2. compress the image
3. crop the picture
Put <script> on bottom
use async and defer keywords to load js script
Add expires and Cache-control in response Header
Gzip
Put <style> on top, for progressive rendering
Minify JavaScript and CSS
Avoid Redirects
Reduce the Number of DOM Elements
Minimize DOM Access
Avoid Empty Image src

HTTP is stateless. The server cannot recognize a visitor after he visits. But we have needs to be able to know the visitor when he visits next time:

Personalization: next time we show him related info, based on his first visits
Session management: after user login, we don’t let him keep logging in when access sensitive data
Tracking: analyzing user behavior, like how many time clicks on which section on the page

III. Session

Session is server-side storage, used to store recent user information, in order to keep a live conversation. Work with

Cookie: store the sessionId in cookie. Every browser bring this ID card when converse with server
Database: if there is too much info, need to store info in Database, like Redis

Although cookies and cache are two ways to store data on client’s machine, but there are difference between cache and cookies and they serve different purposes.

Cookie is used to store information to track different characteristics related to user, while cache is used to make the loading of web pages faster.
Cookies stores information such as user preferences, while cache will keep resource files such as audio, video or flash files.
Typically, cookies expire after some time, but cache is kept in the client’s machine until they are removed manually by the user.

V. What happens when we visit Google.com?

Check if cached already, if so, reload cache content directly
If no cache, then convert the domain name to IP, recursive DNS look up:
- browser cache
- OS cache
- router cache
- ISP cache
- recursive DNS lookup
Browser get the IP, and wrap http payload inside TCP packet, and then to even lower layer, pass to router to the Server
Build up the TCP connect
Browser sends HTTP request to Server
Server send HTTP response with meta info in header to Browser
Browser receives the response header and content
- store cookie, and cache css or js
- render the DoOM tree, CSS-OMTree
- run JavaScript
- Create Render tree
- generate Layout
- painting
Browser keep request external js/ css file from Server, keeps render

VI. Positioning of Elements

https://juejin.im/post/5b52dec0f265da0fa21a8242

https://zhuanlan.zhihu.com/p/25455672

offsetTop
scrollTop
clientHeight

VII. Throttle & Debounce

https://juejin.im/post/5b52dec0f265da0fa21a8242

https://zhuanlan.zhihu.com/p/25455672

VIII. Algorithm

分解质因数，比如给一个数20
输出：
20 = 2 2 5
11 = 11
followup：
输出 20 = 2^2 5
followup2：
反过来输出： 20 = 5 2^2

let t1 = 20
let t2 = 7
let t3 = 81
let t4 = 0
console.log(factors(t1))
console.log(factors(t2))
console.log(factors(t3))
console.log(factors(t4))

function factors(n){
    if(n===null || isNaN(n) || n===0 || !Number.isInteger(n)) 
        return Error("Valid Expected")
    if( n === 1 ) return 1
    
    let res = []
    
    while( n%2 === 0 ){
        res.push(2)
        n /= 2
    }
    
    for( let i = 3; i*i<=n; i+=2 ){
        while(n%i===0){
            res.push(i)
            n /= i
        }
    }
    if(n>1) res.push(n)
    
    let str = ''
    let cnt = 1
    let prev = res[0]
    for( let i = 1; i < res.length; i++ ){
        if(res[i] !== prev){
            if(cnt>1) str += prev+'^'+cnt+'*'
            else      str += prev+'*'
            cnt=1
            prev = res[i]
        }else{
            cnt++
        }
    }
    if(cnt>1) str += prev+'^'+cnt
    else      str += prev
    return str
}

一个字符串的list，输出其中有anagram的字符串。类似leetcode 49，很快最好一遍编译过

Followup: Print lists according to the input order

let test1 = ["eat", "tea", "tan", "ate", "nat", "bat"]
let test2 = ["eat", "tan", "bat"]
let test3 = []
console.log(anagrams(test1))
console.log(anagrams(test2))
console.log(anagrams(test3))



function anagrams(arr){
    let map = new Map()
    arr.forEach(item=>{
        let p = mapping(item)
        if(!map.has(p)){
            map.set(p,[])
        }
        let list = map.get(p)
        list.push(item)
        map.set(p, list)
    })
    
    let res = []
    map.forEach(val=>{
        res.push(val)
    })
    return res
}

function mapping(str){
    let res = new Array(256).fill("-")
    for( let i = 0; i < str.length; i++ ){
        let index = str.charCodeAt(i)
        res[index] = '+'
    }
    return res.join('')
}

Largest rectangle in histogram

/**
 * @param {number[]} heights
 * @return {number}
 */
var largestRectangleArea = function(heights) {
    if(heights === null || heights.length === 0) return 0
    if(heights.length === 1) return heights[0]
    
    let rightFirstSmallerIndices = FirstSmallerIndices(heights, true)
    let leftFirstSmallerIndices = FirstSmallerIndices(heights, false)
    
    let res = 0
    for(let i = 0; i < heights.length; i++){
        let idLeft = leftFirstSmallerIndices[i]
        let idRight = rightFirstSmallerIndices[i]
        res = Math.max(res, heights[i]*(idRight-idLeft-1))
    }
    return res
};


function FirstSmallerIndices(arr, right){
    let res = new Array(arr.length).fill(arr.length)
    let ids = new Array(arr.length).fill(0).map((_,id)=>id)
    
    if(!right){ 
        res = new Array(arr.length).fill(-1)
        ids = ids.map((_,id)=>arr.length-id-1)
    }
    
    let stack = []
    stack.push(ids[0])
    
    for(let i = 1; i<ids.length; i++ ){
        let id = ids[i]

        while(arr[stack[stack.length-1]] > arr[id]){
            let topId = stack.pop()
            res[topId] = id
        }
        stack.push(id)                                                  
    }
    return res
}

LC 85/ 845

不一样的是in addition要给出长方形的坐标，例如左上角点的坐标

/**
 * @param {character[][]} matrix
 * @return {number}
 */
var maximalRectangle = function(matrix) {
    if(matrix === null || matrix.length === 0 || matrix[0].length === 0)
        return 0
    
    let res = 0
    let r = matrix.length
    let c = matrix[0].length
    for(let i = 0; i < r; i++){
        for( let j = 0; j < c; j++ ){
            if(i-1>=0 && matrix[i][j]==="1" ) {
                matrix[i][j] = Number(matrix[i][j])+Number(matrix[i-1][j])
            }else 
                matrix[i][j] = Number(matrix[i][j])
        }
        res = Math.max(res, largestRectangleArea(matrix[i]))
    }
    
    return res
};


function largestRectangleArea(heights) {
    if(heights === null || heights.length === 0) return 0
    if(heights.length === 1) return heights[0]
    
    let rightFirstSmallerIndices = FirstSmallerIndices(heights, true)
    let leftFirstSmallerIndices = FirstSmallerIndices(heights, false)
    
    let res = 0
    for(let i = 0; i < heights.length; i++){
        let idLeft = leftFirstSmallerIndices[i]
        let idRight = rightFirstSmallerIndices[i]
        res = Math.max(res, heights[i]*(idRight-idLeft-1))
    }
    return res
};

function FirstSmallerIndices(arr, right){
    let res = new Array(arr.length).fill(arr.length)
    let ids = new Array(arr.length).fill(0).map((_,id)=>id)
    
    if(!right){ 
        res = new Array(arr.length).fill(-1)
        ids = ids.map((_,id)=>arr.length-id-1)
    }
    
    let stack = []
    stack.push(ids[0])
    
    for(let i = 1; i<ids.length; i++ ){
        let id = ids[i]

        while(arr[stack[stack.length-1]] > arr[id]){
            let topId = stack.pop()
            res[topId] = id
        }
        stack.push(id)                                                  
    }
    return res
}

fisher-yates shuffle

function shuffle(arr){
    let n = arr.length
    while(n>0){
        let randId = Math.floor(Math.random() * n)
        let temp = arr[randId]
        arr[randId] = arr[n-1]
        arr[n-1] = temp
        n--
    }
    return arr
}

shuffle([1,2,3,4,5,6,7,8,9])

LC 304 range sum query - immutab

class NumMatrix {

    private int[][] dp;

    public NumMatrix(int[][] matrix) {
        if(   matrix           == null
           || matrix.length    == 0
           || matrix[0].length == 0   ){
            return;   
        }

        int m = matrix.length;
        int n = matrix[0].length;

        dp = new int[m + 1][n + 1];
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] -dp[i - 1][j - 1] + matrix[i - 1][j - 1] ;
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        int iMin = Math.min(row1, row2);
        int iMax = Math.max(row1, row2);

        int jMin = Math.min(col1, col2);
        int jMax = Math.max(col1, col2);

        return dp[iMax + 1][jMax + 1] - dp[iMax + 1][jMin] - dp[iMin][jMax + 1] + dp[iMin][jMin];    
    }
}

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * int param_1 = obj.sumRegion(row1,col1,row2,col2);
 */

LC 380 insertDeleteGetRandomO(1)
LC 162 find peak element
// Given multiple lists, each list contains few integer numbers

// We want to get all the possible combinations within those lists, with the following condition:

// one combination should contain one and at MOST one element from each list

// Example: input => [[1,2], [3,4]]

// output = [[1, 3], [1, 4], [2, 3], [2, 4]] // 8

要求用两种方法，都先排序，一个是用Index判断去重，还有一个是用set判断去重

问了时间空间复杂度，最好和最坏情况

输入”rft567.908kih000000hh890jug678gtff567”这样包含字母和数字的字符串，找到出线次数最多的数字，print “567 shows two time”。
asdbf-12.456.1asdf12.343.232这样的话，应该返回什么呢？
matrix binary search 用两个二分和一个二分分别实现了下，时间复杂度都是O(logm + logn),
打印树，给一个节点，打印出树的graph
longest increasing subsequence

(2019) Minimum window subsequence

/**
 * @param {string} S
 * @param {string} T
 * @return {string}
 */
var minWindow = function(S, T) {
    
    let minLen = S.length + 1
    let minLeft = 0
    
    let i = 0, j = 0
    while( i < S.length ){
        if( S[i] === T[j] ){
            if( j===T.length-1 ){
                let end = i
                while( j >= 0 ){
                    while( S[i] !== T[j] ) i--
                    i--
                    j--
                }
                i++
                if(minLen > end-i+1){
                    minLen = end-i+1
                    minLeft = i
                }
            }
            j++
        }
        i++
    }
    return minLen===S.length + 1 ? '' : S.slice(minLeft, minLeft+minLen)
};

LCA of deepest leaf nodes in a binary tree

8位String的生成器，要求在A-Z，a-z，0-9，%$&#里挑，每组至少选一个

/*
	1. which digit use which group of character
	2. a method to randomly get a char from its group
	3. fasher-yate shuffle
*/

const UPPERCASE = new Array(26).fill(0).map((_,index)=>String.fromCharCode(index+65))
const LOWERCASE = new Array(26).fill(0).map((_,index)=>String.fromCharCode(index+97))
const NUMBER = new Array(10).fill(0).map((_,index)=>index)
const SYMBOL = new Array(14).fill(0).map((_,index)=>String.fromCharCode(index+33))

const ARRAY = [UPPERCASE, LOWERCASE, NUMBER, SYMBOL]
function generate (n){
    let res = []
    for(let i = 0; i < ARRAY.length; i++)
        res.push(getOne(ARRAY, i))
    
    for( let i = 0; i < n-ARRAY.length; i++ ){
        let type = Math.floor( (Math.random() * ARRAY.length) )
        res.push(getOne(ARRAY, type))
    }
    return shuffle(res).join('')
}

function getOne(ARRAY, type){
    let len = ARRAY[type].length
    let rand = Math.floor(Math.random()*len)
    return ARRAY[type][rand]
}

function shuffle(arr){
    let n = arr.length
    while(n>0){
        let rand = Math.floor(Math.random*n)
        let temp = arr[rand]
        arr[rand] = arr[n-1]
        arr[n-1] = temp
        n--
    }
    return arr
}

console.log(generate(8))

(2019)列车时刻表
A B 1000 1130 （A 到 B，10：00出发， 11：30到达）
B C 1200 1230
A C 1100 1250

求 A 到 C: 1) 最早到达的时间，输出大概是“A C 1000 1230”。 2)若有多条线路同时到达，求最晚出发的列车schedule，输出格式和第一问一样。

https://www.1point3acres.com/bbs/thread-460017-1-1.html
基本上跟 LC 上面 walls and gates 很像，但是有一个agent （起点）和 several goals (终点) 问能不能从一个起点到达所有终点。
矩阵类似这样：
0 0 0 1 1 1
A 1 0 1 G 1
1 0 G 0 1 1
1 0 0 1 0 1

我用recursion写出来然后各种检查typo。最后还是被白人小哥嘲笑worlds打成world。
还有我更改了矩阵内容0->1，被不允许
(2018-12-6) sqrt(n)，最开始我说用brute-force从0到result找，然后刚想说优化用binary search，面试官就表示，如果我的输入是double，怎么办？所以最终的问题变成sqrt(double n, double delta)，需要输出一个在[result-delta, result+delta]范围内的任意一个值，然后其实还是binary search来做。最后还有个bug，这里处理得不是很好，感觉面试官有点儿不高兴，唉。。。然后分析了下时间复杂度，问了问问题，就结束了。。
(2018-12-6)题目是，给两个二叉树s和t，需要判断t是否是s的某一个subtree。
先说了brute-force的方法，然后分析了一下时间复杂度，然后开始优化，当时直觉是用inorder-traverse转化成string来做，但是最开始中间还是有bug，例如
1 2
/ \ \
2 3 和 1，如果仅仅考虑inorder的情况，显然是不对了。

幸好大哥给了点提示，然后顺利写出代码，中间有些小bug，在跑了俩test case后就知道问题所在，然后改完就ok了。大哥人真的很nice，面试体验很棒，后面还跟我介绍了很多他们组的情况以及houzz。
top k visited website this day

this is typical top k . you can create a list of {3, [web1, web2] } , { 2, [web 3 , web 4] } 3 stands for the visited time and web 1 & web 2 stands for the websites . and then you can do the traversal to find the proper results. thanks
完全背包，刚开始理解成了01背包，后来发现他想要完全背包，反正两种都写了
给出一个arr, 如[0,1,0,1,0]，每个1就是一个发电厂，然后给出一个range，比如是2，就是说每个发电厂能cover前后range为2的距离，然后求需要的发电厂的最少数。e.g. [1,1,0], range 为 1 -> [0,1,0]

给的arr里面有1和0，但是最后输出的arr 要把其中某些1变成0，（不知0能否变成1？）从而达到最少数的发电厂

http://www.cs.toronto.edu/~jepson/csc373/tutNotes/cellTower.pdf

Course Schedule III

https://leetcode.com/problems/heaters/description/
LC 65 Valid Number

valid number那道题
“12.3459” -> 12.3459
“ 12.3459 “ -> 12.3459
“12.3 459” -> Exception
“1 2.3459” -> Exception
“12.34x59” -> Exception
“12.34.59” -> Exception
e.g. “+.34” -> 0.34
e.g. “-1.234” -> -1.234这题感觉之前面经没一个说明白详细的。第一，只能扫一遍，trim都不可以用，第二，不能用valueOf这种函数，parse转化不可以。也就是说，只能硬扫记录硬来，不能用stringbuilder去存去做。这题面之前就写了，但没想到限制的这么硬，虽然和lc65差了个e，但难度基本一样。
design calendar class 有 day year month 实现 add (days) return calendar、、
add(num1, num2) 不能用加号。
Merge k sorted arrays
Design Twitter
find median of two sorted array,
LC 85 Maximal Rectangle，一个变化是要求最后返回一个maximal rectangle的identifier。 (需要给用到stack的那个解法 )
设计题，要求返回twitter在过去24小时里最popular的10个单词（任何string）
String Permutation I, Follow Up String Permutation II.
都秒了，
Longest Incresing Subsequence.
强制用JavaScript写一个方法，把一句话中所有的word转换成第一个字符大写的word
LC 227 但是有括号也要考虑。

print a given source to a destination

let adjList = [
    [1,2,3],
    [3],
    [0,1],
    []
]

let s = 2, t = 3
function getAllPaths(adjList, s, t){
    let res = []
    let visited = new Set()
    dfs(s, [])
    return res
    
    function dfs(nodeId, prefix){
        if(nodeId === t){
            res.push([...prefix, nodeId])
            return
        }
        
        let children = adjList[nodeId]
        visited.add(nodeId)
        children.forEach(item=>{
            if(!visited.has(item))
            	dfs(item, [...prefix, nodeId])
        })
        visited.delete(nodeId)
    }
}

console.log(getAllPaths(adjList, s, t))

traverse the graph

let adjList = [
    [1,2,3],
    [3],
    [0,1],
    []
]
let s1 = 0
// console.log(traverse(adjList, s1))
let s2 = 2
// console.log(traverse(adjList, s2))

function traverse(adjList, s){
    let visited = new Set()
    let res = []
    dfs(s)
    return res
    
    function dfs(n){
        res.push(n)
        visited.add(n)
        
        let children = adjList[n]
        children.forEach(item=>{
            if(!visited.has(item)){
                dfs(item)
            }
        })
    }
}

数字恩，假设这是一个恩乘恩的正方形单元网格，给一个圆，半径以及圆心点坐标，求有多少小格子完全在园内？不依不饶：有没有欧恩的解法？

根据圆的坐标很容易找到第一个格子，其部分顶点包含在园内，部分在圆外。以这个格子为起始做dfs，找出所有类似的格子，（这些格子全在圆的边界上）。那么所有有相同x坐标的格子，y坐标差减一就是这两个格子之间一定在园内的格子数。这样traverse by x坐标，累积的y坐标差应该就是在园内的格子数。
欢迎大家补充更优解！！

圆心，半径都是浮点数。我觉得楼上那位同学说的比我的解法好。扫描经过圆心的直径，根据纵坐标算夹在圆内的格子，这样应该是O(n)，比如，圆心是x = 3.4， y = - 3 半径 5.5，那么从， Math.max(0, ceilling(x - r)) 一直扫描到 Math.min(n - 1, floor(x + r)). 对每个 x’, x’ + 1 算有多少格子在园内，格子数的和即为最后园内格子数。

(x - 3.4)^2 + (y + 3)^2 = 5.5^2 带入 x’ 以及 x’ + 1, 得到y的上界yUp y’Up，下界 ydown, y’down，格子数就是，Floor(Math.min(yUp, y’Up, n)) - ceilling(Math.max(ydown, y’down, 0)),

Shell_Smith 发表于 2018-1-18 09:01
不是，如果说n是1的话，那么就有（0，0）（0，1）（1，0）（1，1）四个点围成一个正方形，这个正方形所有 …
假设圆心是(x0, y0)，半径是r的话，把圆分成左右两半分别计算即可：
对于右边一半，遍历 x = x0 + 1, …, x0 + r，对每个x，计算对应的圆上的y值 yt 和 yb，那么横坐标是x且在圆内的点的个数是 floor(yt) - floor(yb)，一旦x到网格外了就停止
对于左边一半同样计算
复杂度是 O(N)
quicksort & merge sort
graph是不是bipartite的，bfs解完了，接下来问时间复杂度，可不可以优化。
https://www.1point3acres.com/bbs/thread-286531-1-1.html
一个unfair coin，怎么disign一个process可以返回同样几率的0和1.
Calculate the distance of bits between two integers.
For example: 1 -> 01; 2 -> 10; dist = 2;
Fibonacci, recursive + non recursive;
file path “/home/./../user/file/.././“大概这样 .表示不动，..表示去上层，要求返回简化的路径，”/user”,stack做
calendar add day

Calendar class（有三个field，year，month，day）和一个数N，实现一个函数，返回N天之后的calendar，譬如说输入是{2017， 3，20}和12，那么返回的是{2017，4， 1}
excel implementation
Given a DAG, a source, a target, and number n, 找出从source到target的长度为n的路径的个数。
given a undirectd and acyclic graph, 一个source和一个target，找出source到target的最长path
是之前面经里有过的一个二维数组最后一个格子是个moving block的那题。应该要用a star算法。。我刷面经的时候就想说要是考到这题我就放弃。。因为之前研究了半天还是觉得太复杂，搞懂了感觉一个小时也写不出来。。结果好死不死的考到了＝。＝当然我是没有放弃的，强行用DFS解了下，但是空间复杂度会很高，小姐姐说最多只能跑个2*2的试试，DFS的话就是你每走一步就把当前棋盘的状态存到一个hashset里，然后要是走到相同状态就不再走下去。反正最后写了100多行跑了个最简单的用例但是感觉有loop，也没时间debug了。
find max number of points in one line + 系统设计（设计一个topic ranking 系统）
有向有环图中找source 到 target 的距离为n的可能性
wordbreak 2 (follow up : NLP problems)

XI. SQL

select count distinct
query要用group by, 然后让我写一个方法，输入income和taxTable可以得出tax. 不是算法题，当时我都震惊了，就是分段函数求和。小哥说就想看下我会不会写code。。估计前面的问答让他对我的能力深感怀疑。。
给了个实际例子要我写了个简单的3个entity的table（one to many & many to many）一个USER有很多ALBUM, 很多PHOTO对应很多album
写SQL: 给一个用户，这个用户有几张照片？
每个相册分开呢？

最后问了几个SQL的问题：

有user，user有photo，怎么建表，大概写一下
写一个SQL查每个user有多少照片